Computational Complexity: A Modern Approach - 国立公園

Computational Complexity: A Modern Approach

#計算複雑性理論

https://images-na.ssl-images-amazon.com/images/I/61Kb8Z2ml-L.jpg

PART ONE: BASIC COMPLEXITY CLASSES

1. The computational model - and why it doesn't matter

2. NP and NP completeness

3. Diagonalization

4. Space complexity

5. The polynominal hierarchy and alternations

6. Boolean circuit

7. Randomized computation

8. Interactive proof

9. Cryptography

10. Quantum computation

11. PCP theorem and hardness of approximation: An introduction

PART TWO: LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS

PART THREE: ADVANCED TOPICS